package com.zhugang.week13.recursion;

/**
 * @program algorithms
 * @description: multiply
 * @author: chanzhugang
 * @create: 2022/11/18 00:01
 */
public class Multiply {

    /**
     * 面试题 08.05 递归乘法
     * https://leetcode.cn/problems/recursive-mulitply-lcci/
     *
     * @param A
     * @param B
     * @return
     */
    public int multiply(int A, int B) {
        /**
         * 思路1：直接for计算加
         * 思路2：递归，转成加法，对半计算
         * A 个 B 相加
         */
        if (A == 1) {
            return B;
        }
        int halfVal = multiply(A / 2, B);
        if (A % 2 == 1) {
            return halfVal + halfVal + B;
        } else {
            return halfVal + halfVal;
        }
    }

    public int multiply2(int A, int B) {
        /**
         * A个B 相加 或者 B个A 相加
         * 个数肯定是越少越好
         */
        int n = Math.min(A, B);
        int k = Math.max(A, B);
        if (n == 1) {
            return k;
        }
        int halfVal = multiply2(n / 2, k);
        if (n % 2 == 1) {
            return halfVal + halfVal + k;
        } else {
            return halfVal + halfVal;
        }

    }
}